package leetcode_61_80;

public class exist_79 {
    /**
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
     * 如果 word 存在于网格中，返回 true ；否则，返回 false 。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
     * 同一个单元格内的字母不允许被重复使用。
     * @param board
     * @param word 仅由大小写英文字母组成
     * @return
     */
    public boolean exist(char[][] board, String word) {
        /**
         *想法是递归回溯处理
         */
        return function(2,1,0,0,board,word);
    }

    /**
     *递归回溯
     * 从第一个开始往后全部在递归里判断
     * 每个元素三个方向
     * 太狗吧繁琐了
     * @param location 当前元素是上一个字符的什么位置，1代表在左，2代表右，3代表的下
     * @param k 当前是第几个字符
     * @param i  当前行
     * @param j 当前列
     * @param board
     * @param word
     * @return
     */
    public boolean function(int location,int k,int i,int j,char[][] board, String word){
        if(k==word.length() && word.charAt(k-1) == board[i][j]) //能到达第k个字母，并且匹配，返回true
            return true;
        int row = board.length,col = board[0].length;
        if(word.charAt(k-1) == board[i][j]){ //如果字母匹配
            if (location == 1){      //在上一个字符左边，只考虑左和下
                if(i==row-1 && j==0){  //已经是左下角
                    if(k!=word.length()-1)
                        return false;
                }else if(j==0) //左边界上，只能往下找
                    return function(3,k+1,i+1,j,board,word);
                else if( i==row-1) //下边界上，只能往左找
                    return function(1,k+1,i,j-1,board,word);
                else   //都不会越界，左和下都可以找
                    return function(3,k+1,i+1,j,board,word) || function(1,k+1,i,j-1,board,word);
            }
            if (location == 2) {     //在上一个字符右边，只考虑右和下
                if (i == row-1 && j == col - 1) {  //已经是右下角
                    if (k != word.length() - 1)
                        return false;
                } else if (i == row-1) //下边界上，只能往右找
                    return function(2, k + 1, i, j + 1, board, word);
                else if (j == col - 1) //右边界上，只能往下找
                    return function(3, k + 1, i +1, j, board, word);
                else   //都不会越界，右和下都可以找
                    return  function(2, k + 1, i, j + 1, board, word) || function(3, k + 1, i +1, j, board, word);
            }
            if (location == 3) {     //在上一个字符下边，左右下都可以
                if(i==row-1 && j==0) //已经是左下角,只能往右找
                    return function(2, k + 1, i, j + 1, board, word);
                else if (i == row-1 && j == col - 1) //已经是右下角,只能往左找
                    return function(1, k + 1, i, j -1, board, word);
                else if (j == 0) //左边界上，只能往下和右找
                    return function(3, k + 1, i+1, j , board, word) || function(2, k + 1, i, j + 1, board, word);
                else if (j == col - 1) //右边界上，只能往左和下找
                    return function(3, k + 1, i +1, j, board, word)|| function(1, k + 1, i, j -1, board, word);
                else if (i== row- 1) //下边界上，只能往左右找
                    return function(1, k + 1, i , j-1, board, word)|| function(2, k + 1, i, j + 1, board, word);
                else   //都不会越界，左右下都可以找
                    return function(3, k + 1, i+1, j , board, word) || function(1, k + 1, i , j-1, board, word) || function(2, k + 1, i, j + 1, board, word);
            }
        }else {  //不匹配
            if (location == 1){      //在上一个字符左边，只考虑左和下
                if(i==row-1 && j==0){  //已经是左下角
                    if(k!=word.length()-1)
                        return false;
                }else if(j==0) //左边界上，只能往下找
                    return function(3,1,i+1,j,board,word);
                else if( i==row-1) //下边界上，只能往左找
                    return function(1,1,i,j-1,board,word);
                else   //都不会越界，左和下都可以找
                    return function(3,1,i+1,j,board,word) || function(1,1,i,j-1,board,word);
            }
            if (location == 2) {     //在上一个字符右边，只考虑右和下
                if (i == row-1 && j == col - 1) {  //已经是右下角
                    if (k != word.length() - 1)
                        return false;
                } else if (i == row-1) //下边界上，只能往右找
                    return function(2, 1, i, j + 1, board, word);
                else if (j == col - 1) //右边界上，只能往下找
                    return function(3, 1, i +1, j, board, word);
                else   //都不会越界，右和下都可以找
                    return  function(2,  1, i, j + 1, board, word) || function(3,  1, i +1, j, board, word);
            }
            if (location == 3) {     //在上一个字符下边，左右下都可以
                if(i==row-1 && j==0) //已经是左下角,只能往右找
                    return function(2, k + 1, i, j + 1, board, word);
                else if (i == row-1 && j == col - 1) //已经是右下角,只能往左找
                    return function(1, k + 1, i, j -1, board, word);
                else if (j == 0) //左边界上，只能往下和右找
                    return function(3,  1, i+1, j , board, word) || function(2,  1, i, j + 1, board, word);
                else if (j == col - 1) //右边界上，只能往左和下找
                    return function(3,  1, i +1, j, board, word)|| function(1,  1, i, j -1, board, word);
                else if (i== row- 1) //下边界上，只能往左右找
                    return function(1, 1, i , j-1, board, word)|| function(2,  1, i, j + 1, board, word);
                else   //都不会越界，左右下都可以找
                    return function(3,  1, i+1, j , board, word) || function(1,  1, i , j-1, board, word) || function(2, 1, i, j + 1, board, word);
            }
        }
        return false;
    }


    /**
     * 官解的递归回溯
     * 把递归放在循环里，遍历判断每一个元素是否可以，递归回溯四个方向
     * 不同方向的 i 和 j 的处理统一到数组中，减少代码冗余
     * @param board
     * @param word
     * @return
     */
    public boolean exist2(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                //起点如果不是word的首字符，那就跳过当前位置，不从这里开始遍历
                if(board[i][j] != word.charAt(0)){
                    continue;
                }
                visited = new boolean[m][n];
                //如果从(i,j)开始遍历能找到word在网络中，则返回true；否则继续从头开始遍历
                if(findWord(board,word,i,j,0,visited)){
                    return true;
                }
            }
        }
        return false;
    }
    int m = 0;
    int n = 0;
    /**
     * 用来判断是否重复判断了某个元素
     */
    boolean[][] visited;
    /**
     * 四个方向时对 i 和 j 的处理
     * 好巧妙的方法，我上面对不同方向的 i 和 j 的处理是通过if else
     * 这里统一到数组中，减少了代码的冗余
     */
    int[][] direct = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    private boolean findWord(char[][] board, String word, int i, int j, int cur,boolean[][] visited){
        //如果cur指针越界了，则证明已经找到与word匹配的所有字符了
        if(cur==word.length()){
            return true;
        }
        //i 和 j 如果越界则该方向返回false
        if(i<0 || j<0 || i>=m || j>=n){
            return false;
        }
        //如果当前网络字符不等于word的第cur个字符，或者当前字符已经被访问，则false
        if(board[i][j] != word.charAt(cur) || visited[i][j]){
            return false;
        }
        //标记该位置已被访问
        visited[i][j] = true;
        //如果从当前点(i,j)散发的四个方向中有一个方向能成功匹配剩下的字母，则可以返回true
        for(int[] dir:direct){
            if(findWord(board,word,i+dir[0],j+dir[1],cur+1,visited)){
                return true;
            }
        }
        //每个方向都不可以时，回溯该位置为未被访问
        visited[i][j] = false;
        //前面如果没有找到完整匹配的结果则返回false
        return false;
    }
}
